package sort.mergesort;

public class MergeSort {

    public static void main(String[] args) {

        int[] nums = new int[100000];
        long start = System.currentTimeMillis();
        for (int k = 0; k < 10; k++) {
            for (int j = 0; j < nums.length; j++) {
                nums[j] = (int) (Math.random() * 1000);
            }
            mergeSort(nums);
        }
        System.out.println("merge sort cost ：" + (System.currentTimeMillis() - start));
    }

    //merge Sort
    public static void mergeSort(int[] nums) {
        int[] temp = new int[nums.length];
        mergeSortDetail(nums, 0, nums.length - 1, temp);
    }

    public static void mergeSortDetail(int[] nums, int start, int end, int[] temp) {
        if (start >= end) {
            return;
        }
        int mid = (start + end) / 2;
        mergeSortDetail(nums, start, mid, temp);
        mergeSortDetail(nums, mid + 1, end, temp);
        //思考：递归到最小维度时；分治思想 （最底层是两个数字比较大小或单个数字；然后再想上合并排序！2 6 7 /3 4）
        merge(nums, start, mid, end, temp);
    }

    public static void merge(int[] nums, int start, int mid, int end, int[] temp) {

        int left = start;
        int right = mid + 1;
        int index = start;
        while (left <= mid && right <= end) {
            if (nums[left] < nums[right]) {
                temp[index++] = nums[left++];   // temp[index] =nums[left]; index++; left++;
            } else {
                temp[index++] = nums[right++];
            }
        }
         //左边单个
        while (left <= mid) {
            temp[index++] = nums[left++];
        }
        //右边单个
        while (right <= end) {
            temp[index++] = nums[right++];
        }

        //替换 （将有序集合重新插入nums集合中）
        for (index = start; index <= end; index++) {
            nums[index]= temp[index];
        }
    }
}
